# define _CRT_SECURE_NO_WARNINGS

//最大公约数与最小公倍数
//什么是最大公约数？————》两个数同时可以除的最大数字（辗转相除）
// 两个数不停的相除，且余数不等于0时，最大公数就是除数
//什么是最小公倍数————》两个数相乘在除以最大公约数
// 
// 
//#include<stdio.h>
//int main()
//{
//	int a = 0, b = 0;
//	scanf("%d%d", &a, &b);
//	int x = a * b;
//	while (a%b)
//	{
//		a = b;
//		b = a % b;
//	}
//	printf("%d是最大公约数\n", b);
//	printf("%d是最小公倍数\n",x / b);
//	return 0;
//}

//最小公倍数还有其他方法：
//1·可以求出两个数中较大的那个数，然后肯定会有这个较大数不断增加的情况下，同时整除a和b，
// 此时这个数就是最小公倍数（效率比较低）
//#include<stdio.h>
//int main()
//{
//	int a = 0, b = 0;
//	scanf("%d%d", &a, &b);
//	int m=a > b ? a : b;
//	while (m)
//	{
//		if (m % a == 0 && m % b == 0)
//		{
//			break;
//		}
//		m++;
//	}
//	printf("%d是最小公倍数\n", m);
//	return 0;
//}
//2·在两个数中任意选择一个数，将它不断乘以一个从开始不断自增的数，这个数肯定会整除另一数

//#include<stdio.h>
//int main()
//{
//	int a = 0, b = 0;
//	scanf("%d%d", &a, &b);
//	int i = 1;
//	while (a * i % b != 0)
//	{
//		i++;
//	}
//	printf("%d为最小公倍数\n", a * i);
//	return 0;
//}


//单身狗

//一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
//
//编写一个函数找出这两个只出现一次的数字。
//
//例如：
//
//有数组的元素是：1，2，3，4，5，1，2，3，4，6
//
//只有5和6只出现1次，要找出5和6.

//我们想这个题目可以想到关于找单身狗1的题目，是找一个单身狗，这个题目与那个本质上是一样的
//
//#include<stdio.h>
//void Find_num(int str[], int len, int* num1, int* num2)
//{
//	int tem = 0;
//	int pos = 0;
//	for (int i = 0; i < len; i++)
//	{
//		 tem ^= str[i];
//	}
//
//	for (int i = 0; i < 32; i++)
//	{
//		if (tem & 1 == 1)
//		{
//			pos = i;
//			break;
//		}
//		tem = tem >> 1;
//	}
//	for (int i = 0; i < len; i++)
//	{
//		if ((str[i] >> pos) & 1 == 1)
//		{
//			*num1 ^= str[i];
//		}
//		else
//		{
//			*num2 ^= str[i];
//		}
//	}
//}
//int main()
//{
//	int str[] = { 1,2,3,4,5,1,2,3,4,6 };
//	int len = sizeof(str) / sizeof(str[0]);
//	int num1 = 0, num2 = 0;
//	 Find_num(str, len, &num1, &num2);
//	printf("%d %d\n", num1, num2);
//	return 0;
//}

//单身狗1
//#include<stdio.h>
//int Find_number(int arr[], int len)
//{
//	int tem = 0;
//	for (int i = 0; i < len; i++)
//	{
//		tem ^= arr[i];
//	}
//	return tem;
//}
//int main()
//{
//	int arr[] = { 1,1,2,3,2,3,5 };
//	int len = sizeof(arr) / sizeof(arr[0]);
//	int ret=Find_number(arr, len);
//	printf("%d",ret);
//	return 0;
//}


//获得月份天数特别注意2月份的特殊
//#include<stdio.h>
//int Print(int str[],int year,int month)
//{
//	int day = str[month];
//	if ((year % 4 == 0 && year % 100 != 0 || year % 400 == 0)&&month==2)
//	{
//		
//			return day = day + 1;
//	}
//	else
//		return day;
//}
//int main()
//{
//	int str[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//	int year = 0, month = 0;
//	scanf("%d%d", &year, &month);
//	int num=Print(str,year,month);
//	printf("%d ", num);
//	return 0;
//}

//转移表——计算器为例
//#include<stdio.h>
                        //设置一个菜单
//void menu()
//{
//	printf("*******************************\n");
//	printf("*** 1.Add        2.Sub      ***\n");
//	printf("*** 3.Mul        4.Div      ***\n");
//	printf("*** 0.exit                  ***\n");
//	printf("*******************************\n");
//
//}
//int Add(int x, int y)
//{
//	return x + y;
//}
//int Sub(int x, int y)
//{
//	return x - y;
//}
//int Mul(int x, int y)
//{
//	return x * y;
//}
//int Div(int x, int y)
//{
//	return x/y;
//}
//int main()
//{
//	int input = 0;
//	int x = 0, y = 0;
//	int ret = 0;
//	do
//	{
//		menu();
//		printf("请做出你的选择——》\n");
//		scanf("%d", &input);
//		switch (input)
//		{
//		case 1:
//			printf("请输入两个整数——>\n");
//			scanf("%d%d", &x, &y);
//			ret = Add(x, y);
//			printf("%d\n", ret);
//			break;
//		case 2:
//			printf("请输入两个整数——>\n");
//			scanf("%d%d", &x, &y);
//			 ret = Sub(x, y);
//			printf("%d\n", ret);
//			break;
//		case 3:
//			printf("请输入两个整数——>\n");
//			scanf("%d%d", &x, &y);
//			 ret = Mul(x, y);
//			printf("%d\n", ret);
//			break;
//		case 4:
//			printf("请输入两个整数——>\n");
//			scanf("%d%d", &x, &y);
//			 ret = Div(x, y);
//			printf("%d\n", ret);
//			break;
//		case 0:
//			printf("退出\n");
//			break;
//		default:
//			printf("输入错误，请重新输入——》\n");
//			break;
//		}
//	} while (input);
//	return 0;
//}


//上面的代码太冗杂了，而且有限制运算
//
//#include<stdio.h>
//void menu()
//{
//        printf("*******************************\n");
//    	printf("*** 1.Add        2.Sub      ***\n");
//    	printf("*** 3.Mul        4.Div      ***\n");
//    	printf("*** 0.exit                  ***\n");
//    	printf("*******************************\n");
//}
//int Add(int x, int y)
//{
//    return x + y;
//}
//int Sub(int x, int y)
//{
//    return x - y;
//}
//int Mul(int x, int y)
//{
//    return x * y;
//}
//int Div(int x, int y)
//{
//    return x / y;
//}
//int main()
//{
//    int x = 0, y = 0;
//    int input = 0;
//    int(*pf[])(int x, int y) = { NULL,Add,Sub,Mul,Div };
//    do
//    {
//        menu();
//        printf("请输入你的选择——》\n");
//        scanf("%d", &input);
//        if (input >= 1 && input <= 4)
//        {
//            printf("请输入你想要计算的两个整数：\n");
//            scanf("%d%d", &x, &y);
//            int ret = (*pf[input])(x, y);
//            printf("%d\n", ret);
//        }
//        else if (input == 0)
//        {
//            printf("退出\n");
//        }
//        else
//        {
//            printf("输入错误，请重新输入——》\n");
//        }
//    } while (input);
//    return 0;
//}

//帮助牛牛计算 1+（1+2）+（1+2+3）+...+(1+2+3+...+n)
//#include<stdio.h>
//int Mul_print(int n)
//{
//    int sum = 0;
//    if (n == 1)
//    return n;
//    else
//    {
//        for (int i = 0; i < n; i++)
//        {
//            sum += i;
//        }
//        return sum + Mul_print(n);
//    }
//}
//int main()
//{
//    int n = 0;
//    scanf("%d", &n);
//    int sum = Mul_print(n);
//    printf("%d", sum);
//    return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int n;
//    int sum = 0;
//    int sum1 = 0;
//    scanf("%d", &n);
//    for (int i = 1; i <= n; i++)
//    {
//        sum = sum + i;
//        sum1 += sum;
//    }
//    printf("%d", sum1);
//    return 0;
//}


//模拟实现strlen
//计算器的方法
//#include<stdio.h>
//#include<string.h>
//#include<assert.h>
//int my_strlen( const char* pr)
//{
//    int count = 0;
//    assert(pr);
//    while(*pr != '\0')
//    {
//        count++;
//        pr++;
//    }
//    return count;
//}
//int main()
//{
//    char arr[] = { "abcdefg" };
//    int ret=my_strlen(arr);
//    printf("%d\n", ret);
//    return 0;
//}


//指针减指针
//#include<stdio.h>
//#include<string.h>
//#include<assert.h>
//int my_strlen( const char* pa)
//{
//    assert(pa);
//    char* pc = pa;
//    while (*pa != '\0')
//    {
//        pa++;
//    }
//    return pa - pc;
//}
//int main()
//{
//    char arr[] = { "hello world!" };
//    int ret=my_strlen(arr);
//    printf("%d\n", ret);
//    return 0;
//}

//不创建临时变量
//#include<stdio.h>
//#include<string.h>
//#include<assert.h>
//int my_strlen(char* pa)
//{
//    assert(pa);
//    if (*pa != '\0')
//    {
//        return 1 + my_strlen(pa + 1);
//    }
//}
//int main()
//{
//    char arr[] = { "hello world!" };
//    int ret=my_strlen(arr);
//    printf("%d\n", ret);
//    return 0;
//}

//模拟实现strcpy
//返回的是初始地址，遇到\0就停止

//#include<stdio.h>
//#include<assert.h>
//char* my_strcpy( char* ps, const char* pa)//格式
//{
//    assert(ps!=NULL);
//    assert(pa!=NULL);
//    char* pet = ps;
//    while (*ps= * pa)
//    {
//        pa++;
//        ps++;
//    }
//    return pet;
//}
//int main()
//{
//    char arr[] = { "adcefg" };
//    char ste[200] = { 0 };
//    char* pet=my_strcpy(ste, arr);
//    printf("%s\n", pet);
//    return 0;
//}

//模拟实现strcat

//#include<stdio.h>
//#include<assert.h>
//char* my_strcat(char* ps,  const char* pa)
//{
//    assert(ps != NULL);//不能是空指针
//    assert(pa != NULL);
//    char* ret = ps;
//    while (*ps != '\0')
//    {
//        ps++;
//    }
//    while (*ps = *pa)
//    {
//        ps++;
//        pa++;
//    }
//    return ret;//返回地址
//}
//int main()
//{
//    char str[100] = { "abc" };//注意确保不要栈溢出
//    char arr[] = { "wefd" };
//    char*pat=my_strcat(str, arr);
//    printf("%s\n", pat);
//    return 0;
//}

//杨辉三角

//#include<stdio.h>
//void S_yanghui(int arr[][4],int n)
//{
//    for (int i = 0; i <n ; i++)
//    {
//        for (int j = 0; j <= i; j++)
//        {
//            if (j == 0 || j == i)
//                arr[i][j] = 1;
//            else
//            {
//                arr[i][j] = arr[i - 1][j - 1] + arr[i-1][j];
//            }
//        }
//       
//    }
//}
//void Print(int arr[][4], int n)  //i是横，j是竖，竖不可以省略
//{
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j <= i; j++)
//        {
//            printf("%d ", arr[i][j]);
//        }
//        printf("\n");
//    }
//}
//int main()
//{
//    int arr[5][5] = { 0 };//自己写的时候的难点在于这个地方不知道怎么定义变量
//    S_yanghui(arr,5);
//    Print(arr,5);//不一定是五，可以是其他数字
//    return 0;
//}

//有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，
// 请编写程序在这样的矩阵中查找某个数字是否存在。

//#include<stdio.h>
//void Junxing(int arr[][4], int x,int y,int key)
//{
//    int i = 0, j = y - 1;
//    while (i < x && y >= 0)
//    {
//        if (arr[i][j] > key)
//        {
//            j--;
//        }
//        else if (arr[i][j] < key)
//        {
//            i++;
//        }
//        else
//        {
//            printf("找到了\n");
//            break;
//        }
//    }
//}
//int main()
//{
//    int arr[][4] = { {1,2,3,4},{2,3,4,5},{3,4,5,6},{4,5,6,7} };
//    Junxing(arr, 4,4,5);
//    return 0;
//}


//写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

//例如：给定s1 = AABCD和s2 = BCDAA，返回1
//
//给定s1 = abcd和s2 = ACBD，返回0.
//
//AABCD左旋一个字符得到ABCDA
//
//AABCD左旋两个字符得到BCDAA
//
//AABCD右旋一个字符得到DAABC


//#include<stdio.h>
//int Find_num(char* p1, char* p2)
//{
//    char tem[1000] = { 0 };
//    strcpy(tem, p1);
//    strcat(tem, p1);
//    char* str = strstr(tem, p2);
// 
 //strstr如果返回值为空（NULL），证明不存在，如果返回值不是空，则证明存在
// 不为空返回的是p2在tem中的地址
// 
//    if (str != NULL)
//    {
//        return 1;
//    }
//    else
//    {
//        return 0;
//    }
//}
//int main()
//{
//    char s1[] = "AABCD";
//    char*s2 = "BCDAA" ;
//   int ret= Find_num(s1, s2);
//   printf("%d\n", ret);
//   return 0;
//}

//#include<stdio.h>
//int main()
//{
//    int a[5] = { 5, 4, 3, 2, 1 };
//    int* ptr = (int*)(&a + 1);
//    printf("%d,%d", *(a + 1), *(ptr - 1));
//    return 0;
//}


//int main()
//{
//    int aa[2][5] = { 10,9,8,7,6,5,4,3,2,1 };
//    int* ptr1 = (int*)(&aa + 1);
//    int* ptr2 = (int*)(*(aa + 1));
//    printf("%d,%d", *(ptr1 - 1), *(ptr2 - 1));
//    return 0;
//}

